#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int row = mat.size(), col = mat[0].size();
        vector<vector<int>> prefix(row + 1, vector<int>(col + 1, 0));
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + mat[i][j];
            }
        }
        vector<vector<int>> res(row, vector<int>(col, 0));
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                int x = min(i + k, row - 1) + 1, y = min(j + k, col - 1) + 1;
                int a = max(i - k, 0), b = max(j - k, 0);
                res[i][j] = prefix[x][y] - prefix[x][b] - prefix[a][y] + prefix[a][b];
            }
        }
        return res;
    }
};